#include<stdio.h>
#include<stdlib.h>
struct ListNode {
    int data;
    struct ListNode *next;
};
//struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
//{
//    if(head->next==NULL)
//    {
//        free(head);
//        return NULL;
//    }
//    struct ListNode* fast=head;
//    struct ListNode* slow=head;
//    while(n--)
//    {
//        if(fast!=NULL)
//        fast=fast->next;
//    }
//
//
//    if(fast!=NULL)
//    {
//        while(fast->next)
//        {
//            fast=fast->next;
//            slow=slow->next;
//        }
//        struct ListNode* next=slow->next;
//        slow->next=next->next;
//        free(next);
//    }
//    else
//    {
//        head=slow->next;
//        free(slow);
//    }
//
//    return head;
//}


struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode*n1=NULL;
    struct ListNode*n2=head;
    while(n2)
    {
        struct ListNode*next=n2->next;
        n2->next=n1;
        n1=n2;
        n2=next;
    }
    return n1;
}
struct ListNode* rotateRight(struct ListNode* head, int k)
{
    //1，快慢指针
    //2，快指针走逆置步，慢指针在走
    //3，断开链接，逆置断开的链表，
    //4，插入到头节点前，成为新链表
    //(1)
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    int count =0;
    while(fast)
    {
        count++;
        fast=fast->next;
    }
    k=k%count;
    fast=head;
    while(k--)
    {
        fast=fast->next;
    }
    //(2)
    while(fast->next)
    {
        fast=fast->next;
        slow=slow->next;
    }

    //(3)
    struct ListNode*newnode=slow->next;//老头
    struct ListNode*tail=newnode;
    slow->next=NULL;
    while(tail->next)
    {
        tail=tail->next;
    }
    tail->next=head;
    head=newnode;

    return head;
}
int main()
{
    struct ListNode*n1= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n2= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n3= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n4= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n5= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n6= (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->data=1;
    n2->data=2;
    n3->data=3;
    n4->data=4;
    n5->data=5;


    n1->next=n2;
    n2->next=n3;
    n3->next=NULL;
    n4->next=n5;
    n5->next=NULL;


    struct ListNode*ret=rotateRight(n1,4);

    return 0;
}